#include "stack_queue.h"

void MyStack::printStack(){
    listNode* p = topNode;
    while(p != first){
        if(p->before == first)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->before;
        
    }
}

MyStack::MyStack()
{
    first=topNode=new listNode;
    stackSize=0;
};
MyStack::~MyStack(){};
bool MyStack::push(const int &num)
{
    topNode->next=new listNode;
    topNode->next->before=topNode;
    topNode=topNode->next;
    topNode->data=num;
    stackSize++;
    return true;
}
bool MyStack::pop(int &item)
{
    if(stackSize==0)return false;
    stackSize--;
    item=topNode->data;
    listNode* p=topNode;
    topNode=topNode->before;
    topNode->next=NULL;
    delete p;
    return true;
}
bool MyStack::getTop(int &item)
{
    if(stackSize==0)return false;
    item=topNode->data;
    return true;
}
stacker::stacker(const int &n)
{
    maxcapacity = n;
    s = new string[n];
    topn = 0;
}
stacker::~stacker() {}
int stacker::size()
{
    return topn;
}
bool stacker::empty()
{
    return topn == 0;
}
bool stacker::full()
{
    return topn == maxcapacity;
}
void stacker::push(string a)
{
    if (!full())
        s[topn++] = a;
}
void stacker::pop()
{
    if (!empty())
        topn--;
}
string stacker::top()
{
    return s[topn - 1];
}
string *stacker::output()
{
    string *s = new string[topn + 1];
    for (int i = topn - 1; i >= 0; i--)
    {
        s[i] = top();
        pop();
    }
    return s;
}
MyQueue::MyQueue(const int &s)
{
    first=cnt=last=new listNode;
    capacity=s-1;
};
MyQueue::~MyQueue(){};
bool MyQueue::enQueue(const int &num)
{
    if(size==capacity)return false;
    last->next=new listNode;
    last->next->before=last;
    last=last->next;
    last->data=num;
    size++;
    return true;
}
bool MyQueue::deQueue(int &item)
{
    if(first->next==NULL)return false;
    size--;
    listNode *p=first->next;
    item=p->data;
    first->next=p->next;
    if(first->next!=NULL)first->next->before=first;
    delete p;
    return true;
}
bool MyQueue::getFront(int &item)
{
    if(first==last)return false;
    item=first->next->data;
    return true;
}
bool MyQueue::isFull()
{
    return size==capacity;
}
void MyQueue::printQueue()
{
    listNode *p=first->next;
    for(;p!=last;p=p->next)
    {
        cout<<p->data<<",";
    }
    cout<<last->data<<endl;
    return;

}
bool judge(const string s1)
{
    int size = s1.size();
    int pairnum = 0;
    for (int i = 0; i < size; i++)
    {
        if (!((s1[i] >= '0' && s1[i] <= '9') || s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/' || s1[i] == '(' || s1[i] == ')'))
            return false;
        if(i+1<size)
        {
            if(s1[i]=='/'&&s1[i+1]=='0')return false;
        }
    }
    if ((s1[0] < '0' || s1[0] > '9') && s1[0] != '(')
        return false;
    else if ((s1[size - 1] < '0' || s1[size - 1] > '9') && s1[size - 1] != ')')
        return false;
    else
    {
        int mark = 0; // 0表示前一位为符号加减乘除�?1表示前一位为数字,2表示前一位为左括�?,3表示前一位为右括�?
        for (int i = 0; i < size; i++)
        {
            switch (mark)
            {
            case 0:
                if (s1[i] != '(' && (s1[i] < '0' || s1[i] > '9'))
                    return false;
                if (s1[i] == '(')
                    pairnum++, mark = 2;
                else
                    mark = 1;
                break;
            case 1:
                if (s1[i] == '(')
                    return false;
                if (s1[i] >= '0' && s1[i] <= '9')
                    mark = 1;
                else if (s1[i] == ')')
                    mark = 3, pairnum--;
                else
                    mark = 0;
                break;
            case 2:
                if ((s1[i] < '0' || s1[i] > '9') && s1[i] != '(')
                    return false;
                if (s1[i] == '(')
                    mark = 2, pairnum++;
                else
                    mark = 1;
                break;
            case 3:
                if (s1[i] != '+' && s1[i] != '-' && s1[i] != '*' && s1[i] != '/' && s1[i] != ')')
                    return false;
                if (s1[i] == ')')
                    mark = 3, pairnum--;
                else
                    mark = 0;
            }
        }
        if (pairnum == 0)
            return true;
        else
            return false;
    }
}

int exchange(string s)
{
    if (s == "(")
        return 0;
    else if (s == "*" || s == "/")
        return 2;
    else if (s == "+" || s == "-")
        return 1;
    else if (s == ")")
        return 0;
    else if (s == "#")
        return -1;
    return 10;
}
int check(string a, string b) // 新入栈符号，上一栈符号
{
    if (exchange(a) == 0)
        return 2;
    else if (exchange(a) > exchange(b))
        return 1;
    return 0;
}
void operate(const string s, stacker &num, stacker &op)
{
    if (s == "#") // 读到井号表示算式结束，运算符栈净空
    {
        while (!op.empty())
        {
            num.push(op.top());
            op.pop();
        }
        num.pop(); // #去了
    }
    else if (s == "(")
    {
        op.push(s);
        return;
    }
    else
    {
        if (check(s, op.top()) == 2)
        {
            while (op.top() != "(")
            {
                num.push(op.top());
                op.pop();
            }
            op.pop();
            return;
        }
        else if (check(s, op.top()) == 1)
        {
            op.push(s);
            return;
        }
        else
        {
            while (check(s, op.top()) == 0)
            {
                num.push(op.top());
                op.pop();
            }
            op.push(s);
            return;
        }
    }
}
double calc(string *num, int n,bool &check)
{
    stacker as(n);
    for (int i = 0; i < n; i++)
    {
        if (num[i] != "+" && num[i] != "-" && num[i] != "*" && num[i] != "/")
            as.push(num[i]);
        else
        {
            string a = as.top();
            as.pop();
            string b = as.top();
            as.pop();
            istringstream ss(a); // string转int
            istringstream sn(b);
            double num1, num2;
            ss >> num1;
            sn >> num2;
            double ans = 0.0;
            if (num[i] == "+")
                ans = 1.0 * (num2 + num1);
            else if (num[i] == "-")
                ans = 1.0 * (num2 - num1);
            else if (num[i] == "*")
                ans = 1.0 * num2 * num1;
            else if (num[i] == "/")
                if(num1!=0)ans = 1.0 * num2 / num1;
                else {check=0;return 0;}
            string p;
            ostringstream sf; // int转string
            sf << ans;
            p = sf.str();
            as.push(p);
        }
    }
    string numfinal = as.top();
    istringstream sg(numfinal);
    double ansfinal;
    sg >> ansfinal;
    return ansfinal;
}
void trim(string &s)
{
    int index = 0;
    if (!s.empty())
    {
        while ((index = s.find(' ', index)) != string::npos)
        {
            s.erase(index, 1);
        }
    }
}
bool postfixExpression(const string &s_, string &s2)
{
    if (!judge(s_))
    {
        s2 = "Expression is wrong!";
        return false;
    }
    string s=s_;
    s += "#";
    int slength = s.length();
    stacker num(slength);
    stacker op(slength);
    op.push("#");
    // cout<<op.top()<<endl;
    string ns;
    for (int i = 0; i < slength; i++)
    {

        if (s[i] >= '0' && s[i] <= '9')
        {
            ns += s[i];
        }
        else
        {
            if (ns != "")
                num.push(ns);
            ns = "";
            string opr = "";
            opr += s[i];
            operate(opr, num, op);
        }
    }
    int n = num.size();
    string *snew = new string[n + 1];
    snew = num.output();
    s2="";
    for(int i=0;i<n;i++)
    {
        s2=s2+snew[i];
    }
    return true;
};
bool expressionVal(const string &s_, int &result)
{
    if(!judge(s_)){result=0;return false;}
    string s=s_;
    s += "#";
    int slength = s.length();
    stacker num(slength);
    stacker op(slength);
    op.push("#");
    // cout<<op.top()<<endl;
    string ns;
    for (int i = 0; i < slength; i++)
    {

        if (s[i] >= '0' && s[i] <= '9')
        {
            ns += s[i];
        }
        else
        {
            if (ns != "")
                num.push(ns);
            ns = "";
            string opr = "";
            opr += s[i];
            operate(opr, num, op);
        }
    }
    int n = num.size();
    string *snew = new string[n + 1];
    snew = num.output();
    bool checker=1;
    result=calc(snew,n,checker);
    if(checker)return true;
    else return false;
}
void yanghui(const int &n)
{
    MyQueue q(1000000);
    q.enQueue(0);
    q.enQueue(1);
    int is=-1;
    for(int i=1,u,t;is<=n;i++)
    {
        q.deQueue(u);
        if(u==0)
        {
            q.enQueue(0);
            is++;
            if(is!=0&&is!=1)cout<<endl;
        }
        q.getFront(t);
        if(u!=0&&is!=0){cout<<u;
        if(t!=0)cout<<",";}
        q.enQueue(u+t);
    }

}
